package cn.yuemouren.dynamicprogramming;

/**
 * <p>
 * 0-1背包问题（回溯算法、迭代均能实现，下面提供是迭代算法）
 * </p>
 *
 * @author timi
 * @date 2021/5/14 上午9:11
 **/
public class ZeroToOneKnapsackProblem {

    /**
     * 寻找背包能装物品最大重量（利用一维数组）
     *
     * @param weights     重量集合
     * @param loadBearing 承重量
     *
     * @return
     */
    public Integer knapsack1(int[] weights, int loadBearing) {
        int length = weights.length;
        //用来保存最大可装最大质量
        boolean[] dp = new boolean[loadBearing + 1];
        dp[0] = true;
        dp[weights[0]] = true;
        for (int i = 1; i < length; i++) {
            //将第j个物品放入背包中
            for (int j = loadBearing - weights[i]; j >= 0; j--) {
                // weights[i] 匹配哪些与当前重量相加后能装入背包的数量
                //从大到小是避免一些重复情况
                if (dp[j]) {
                    dp[j + weights[i]] = true;
                }
            }
        }
        for (int i = loadBearing; i >= 0; i--) {
            if (dp[i]) {
                return i;
            }
        }
        return 0;
    }

    /**
     * 寻找背包能装物品最大重量（利用二维数组）
     *
     * @param weights     重量集合
     * @param loadBearing 承重量
     *
     * @return
     */
    public Integer knapsack2(int[] weights, int loadBearing) {
        int length = weights.length;
        boolean dp[][] = new boolean[length][loadBearing + 1];
        //初始化
        dp[0][0] = true;
        dp[0][weights[0]] = true;

        for (int i = 1; i < length; i++) {
            //不放入第i个物品
            for (int j = 0; j <= loadBearing; j++) {
                if (dp[i - 1][j]) {
                    dp[i][j] = dp[i - 1][j];
                }
            }
            //放入第i个物品
            for (int j = 0; j <= loadBearing - weights[i]; j++) {
                if (dp[i - 1][j]) {
                    dp[i][j + weights[i]] = true;
                }
            }
        }
        for (int i = loadBearing; i >= 0; i--) {
            if (dp[length - 1][i]) {
                return i;
            }
        }
        return 0;
    }

    /**
     * 在重量固定的情况下，能获得的最大价值(迭代一)
     *
     * @param weights     重量数组
     * @param values      价值数组
     * @param loadBearing 可装容量
     *
     * @return
     */
    public Integer maximumValue1(int[] weights, int[] values, int loadBearing) {
        int length = weights.length;
        int dp[][] = new int[length][loadBearing + 1];
        //初始化哨兵
        dp[0][0] = 0;
        dp[0][weights[0]] = values[0];

        for (int i = 1; i < length; i++) {

            //不装第i个
            for (int j = 0; j <= loadBearing; j++) {
                if (dp[i - 1][j] >= 0) {
                    dp[i][j] = dp[i - 1][j];
                }
            }

            //装第i个
            for (int j = 0; j <= loadBearing - weights[i]; j++) {
                if (dp[i - 1][j] >= 0) {
                    int v = dp[i - 1][j] + values[i];
                    if (v > dp[i][j + weights[i]]) {
                        dp[i][j + weights[i]] = v;
                    }
                }
            }
        }

        Integer maxValue = Integer.MIN_VALUE;
        for (int i = loadBearing; i >= 0; i--) {
            if (dp[length - 1][i] > maxValue) {
                maxValue = dp[length - 1][i];
            }
        }
        return maxValue;
    }

    private Integer maxValue = Integer.MIN_VALUE;

    /**
     * 在重量固定的情况下，能获得的最大价值(递归一)
     *
     * @param weights       重量数组
     * @param currentWeight 当前重量
     * @param values        价值数组
     * @param currentValue  当前价值
     * @param loadBearing   可装容量
     * @param curr          当前位置
     * @param n             物品数量
     *
     * @return
     */
    public Integer maximumValue2(int[] weights, int currentWeight, int[] values, int currentValue, int loadBearing,
                                 int curr, int n) {
        //结束条件
        if (currentWeight == loadBearing || curr == n) {
            if (currentValue > maxValue) {
                maxValue = currentValue;
            }
            return maxValue;
        }

        //不放第curr个物品
        maximumValue2(weights, currentWeight, values, currentValue, loadBearing, curr + 1, n);

        if (loadBearing >= currentWeight + weights[curr]) {
            Integer newCurrentValue = currentValue + values[curr];
            Integer newCurrentWeight = currentWeight + weights[curr];
            //放第curr个物品
            maximumValue2(weights, newCurrentWeight, values, newCurrentValue, loadBearing,
                        curr + 1, n);
        }
        return maxValue;
    }

    public static void main(String[] args) {
        int[] weights = {1, 2, 3, 5, 2};
        int[] values = {3, 4, 8, 9, 6};
        ZeroToOneKnapsackProblem problem = new ZeroToOneKnapsackProblem();
        Integer weight1 = problem.knapsack1(weights, 9);
        System.out.println(weight1);
        Integer weight2 = problem.knapsack2(weights, 9);
        System.out.println(weight2);
        Integer value1 = problem.maximumValue1(weights, values, 9);
        System.out.println(value1);
        Integer value2 = problem.maximumValue2(weights,0,values,0,9,0,5);
        System.out.println(value2);
    }
}
